/**
* Created with CLion.
* User:Lenovo
* Date:2023-06-03
* Time:1:50
* Description:链式二叉树
*/

#include "BinaryTree.h"

BTNode *BuyNode(BTDataType x)
{
    BTNode *node = (BTNode *)malloc(sizeof(BTNode));
    if (node == NULL)
    {
        perror("malloc failed");
        return NULL;
    }

    node -> data = x;
    node -> left = NULL;
    node -> right = NULL;

    return node;
}

BTNode *CreateBinaryTree()
{
    BTNode *node1 = BuyNode(1);
    BTNode *node2 = BuyNode(2);
    BTNode *node3 = BuyNode(3);
    BTNode *node4 = BuyNode(4);
    BTNode *node5 = BuyNode(5);
    BTNode *node6 = BuyNode(6);
    BTNode *node7 = BuyNode(7);

    node1 -> left = node2;
    node2 -> left = node3;
    node1 -> right = node4;
    node4 -> left = node5;
    node4 -> right = node6;
    node5 -> left = node7;

    return node1;
}

void PrevOrder(BTNode *root) // 递归的构成：子问题和返回条件
{
    if (root == NULL) // 空树不用再分解 - 返回条件
    {
        printf("N -> ");
        return;
    }

    printf("%d -> ", root -> data);
    PrevOrder(root -> left);// 子问题
    PrevOrder(root -> right);
}

void InOrder(BTNode *root)
{
    if (root == NULL)
    {
        printf("N -> ");
        return;
    }

    InOrder(root -> left);
    printf("%d -> ", root -> data);
    InOrder(root -> right);
}

void PostOrder(BTNode *root)
{
    if (root == NULL)
    {
        printf("N -> ");
        return;
    }

    PostOrder(root -> left);
    PostOrder(root -> right);
    printf("%d -> ", root -> data);
}

int BTreeSize(BTNode *root)
{
    if (root == NULL)
    {
        return 0;
    }

    return 1 + BTreeSize(root -> left) + BTreeSize(root -> right);
    // 分治思想：分而治之，让下一层级的人来干活
}

int BTreeLeafSize(BTNode *root)
{
    if (root == NULL)
    {
        return 0;
    }

    return (root -> left == NULL && root -> right == NULL) ?
    1 :
    BTreeLeafSize(root -> left) + BTreeLeafSize(root -> right);
}

int BTreeHeight(BTNode *root)
{
    if (root == NULL)
    {
        return 0;
    }

    int leftH = BTreeHeight(root -> left);
    int rightH = BTreeHeight(root -> right);
    
    return 1 + MAX(leftH, rightH);
}
// 本质上来看，求 Size 和 Height 都是一种后序遍历
// 注意：不能 return BTreeHeight(root -> left) > BTreeHeight(root -> right) ? BTreeHeight(root -> left) + 1 : BTreeHeight(root -> right) + 1
// 上面这种方式会让整体的时间复杂度以指数级别增长
// 校长 -> 院长 -> 老师 -> 班长 -> 学生    每层都会丢一次数据

int BTreeLevelKSize(BTNode *root, int k)
{
    assert(k > 0);

    if (root == NULL)
    {
        return 0;
    }

    if (k > 1)
    {
        return BTreeLevelKSize(root -> left, k - 1) + BTreeLevelKSize(root -> right, k - 1);
    }
    else
    {
        return 1;
    }
}

BTNode *BTreeFind(BTNode *root, BTDataType x)
{
    if (root == NULL)
    {
        return NULL;
    }

    if (root -> data == x)
    {
        return root;
    }

    BTNode *tmp;
    if ((tmp = BTreeFind(root -> left, x)) != NULL)
    {
        return tmp;
    }
    else if ((tmp = BTreeFind(root -> right, x)) != NULL)
    {
        return tmp;
    }

    return NULL;
}

void LevelOrder(BTNode *root)
{
    Queue q;
    QueueInit(&q);

    if (root)
    {
        QueuePush(&q, root);
    }

    while (!QueueEmpty(&q)) // 结束条件：队列为空
    {
        BTNode *front = QueueFront(&q);
        QueuePop(&q);

        printf("%d -> ", front -> data);

        if (front -> left)
        {
            QueuePush(&q, front -> left);
        }
        if (front -> right)
        {
            QueuePush(&q, front -> right);
        }
    }

    printf("\n");
}

bool BTreeComplete(BTNode *root)
{
    Queue q;
    QueueInit(&q);
    
    if (root == NULL)
    {
        return true;
    }
    else
    {
        QueuePush(&q, root);
    }

    while (!QueueEmpty(&q))
    {
        BTNode *front = QueueFront(&q);
        QueuePop(&q);

        // 遇到空就跳出
        if (front == NULL)
        {
            break;
        }

        QueuePush(&q, front -> left);
        QueuePush(&q, front -> right);
    }

    // 检查后面的结点有没有非空，如果有，就不是完全二叉树
    while (!QueueEmpty(&q))
    {
        BTNode *front = QueueFront(&q);
        QueuePop(&q);

        if (front)
        {
            QueueDestroy(&q);
            return false;
        }
    }

    QueueDestroy(&q);
    return true;
}

void BTreeDestroy(BTNode *root)
{
    if (root == NULL)
    {
        return;
    }

    BTreeDestroy(root -> left);
    BTreeDestroy(root -> right);

    free(root);
}







